Shivam Mani Tripathi 11110096

Here's the code that Sir gave:


In [7]:
#-----------Node Definitation-------------
class Node():
    def __init__(self,value):
        self.val=value
        self.next=None
    
#-----------Linked List Definition--------
class LinkedList():
    def __init__(svayam):
        svayam.head=None
        
    def insert(self,val):
        temp=Node(val)
        temp.next=self.head
        self.head=temp
        
    def printL(self):
        
        temp=self.head
        print "Head <--",
        while temp!=None:
            print temp.val, "<--",
            temp=temp.next
        print "Tail\n"
            
    def delete(self,v):
        if self.head == None:
            print "Empty List"
            return
        if self.head.val==v:
            self.head=self.head.next
            return
        prev=self.head
        cur=self.head.next
        while cur!=None and cur.val!=v:
            cur=cur.next
            prev=prev.next
        if cur==None:
            print "Not found"
        else:
            prev.next=cur.next

def print_tree(root):
    '''Print the tree rooted at root.''' 
    print_helper(root, "")

def print_helper(root, indent):
    '''Print the tree rooted at BTNode root. Print str indent (which
    consists only of whitespace) before the root value; indent more for the
    subtrees so that it looks nice.'''
    if root is not None:
        print_helper(root.right, indent + "   ")
        print  "  " +indent + "/"
        print indent + str(root.val)
        print "  " +indent + "\\"
        print_helper(root.left, indent + "   ")

class TreeNode:
    def __init__(self,  val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None
        
#--------- Menu --------------------
ll=LinkedList()
option = 0
while option != 4:
    print "1. Add 2. Delete 3. Print 4. Exit"
    option=input("Option :")
    if option==1:
        value=input("What Value to add: ")
        ll.insert(value)
    elif option==2:
        value=input("What Value to delete: ")
        ll.delete(value)
    elif option==3:
        ll.printL()
    elif option==4:
        break
    else:
        print "Wrong Option"


1. Add 2. Delete 3. Print 4. Exit
Option :4

Runner Loop

Question One

Q1. Linked List in Sorted order In a ordinary linked list the elements does not have any order. Thus if we want to sort the elements in a linked list it might take O(n log n) time. But if the elements are stored in sorted order the runtime can be reduced. Write a program to store elements in sorted order. Your program must support the following functions a) Insertion (this is the place where you need to store the incoming element in its correct place) b) Search if an element is present in the list c) Deletion (only one occurrence is deleted) e) Print (prints the list in sorted order). The program should show a menu to the user

  1. Insert
  2. Search
  3. Delete
  4. Print
  5. Exit

If the user picks 1, your program should then ask Value of the new element ?: , etc. Once an operation is finished it must go back to the menu. Example of a menu based program is given below. (filename: LinkedList)


In [4]:
from random import randint

class SortedLinkedList(LinkedList):
    def __init__(svayam):
        svayam.head=None
        svayam.first_node = None
    
    def insert(self,val):
        temp=Node(val)
        temp_head = self.head
        if self.head == None: 
            self.first_node = temp
            self.head = temp
            return None
        temp_head_prev = None
        while temp_head!=None  and temp_head.val < val:
            temp_head_prev = temp_head
            temp_head = temp_head.next
        temp.next = temp_head
        if temp_head_prev != None: 
            temp_head_prev.next = temp
        else: self.first_node =temp 
        self.head=self.first_node
        
#--------- Menu --------------------
ll=SortedLinkedList()
option = 0
while option != 5:
    print "1. Add 2. Delete 3. Print 4. Random Testing  5. Exit"
    option=input("Option :")
    if option==1:
        value=input("What Value to add: ")
        ll.insert(value)
    elif option==2:
        value=input("What Value to delete: ")
        ll.delete(value)
    elif option==3:
        ll.printL()
    elif option == 4:
        print "Random Sequence: ",
        for i in range(15):
            num = randint(0,9)
            print num," ,",
            ll.insert(num)
        print "\n"
        ll.printL()
    elif option==5:
        break
    else:
        print "Wrong Option"


1. Add 2. Delete 3. Print 4. Random Testing  5. Exit
Option :4
Random Sequence: 
8  , 7  , 2  , 2  , 6  , 3  , 5  , 2  , 2  , 0  , 6  , 8  , 8  , 7  , 1  , 

Head <-- 0 <-- 1 <-- 2 <-- 2 <-- 2 <-- 2 <-- 3 <-- 5 <-- 6 <-- 6 <-- 7 <-- 7 <-- 8 <-- 8 <-- 8 <-- Tail

1. Add 2. Delete 3. Print 4. Random Testing  5. Exit
Option :2
What Value to delete: 2
1. Add 2. Delete 3. Print 4. Random Testing  5. Exit
Option :3
Head <-- 0 <-- 1 <-- 2 <-- 2 <-- 2 <-- 3 <-- 5 <-- 6 <-- 6 <-- 7 <-- 7 <-- 8 <-- 8 <-- 8 <-- Tail

1. Add 2. Delete 3. Print 4. Random Testing  5. Exit
Option :5

Question 2: Stack Using Linked List

The array implementation of stack cannot handle more elements than the size of the array. This can be avoided if the stack is implemented using a linked list. Support Push, Pop and IsEmpty operations. Write a menu based program. (filename:StackUsingLinkedList)


In [5]:
from random import randint


class StackUsingLinkedList(LinkedList):
    def __init__(svayam):
        svayam.head=None
        
    def isEmpty(self):
        if self.head == None:
            return True
        return False
    
    def Push(self, val):
        self.insert(val)
        
    def Pop(self):
        if(self.isEmpty()):
             
            return "Underflow Error"
        else:
            val = self.head.val
            self.head = self.head.next
        return val

stack=StackUsingLinkedList()
option = 0
while option != 5:
    print "\n1. Push 2. Pop 3. Print 4. Random Testing  5. Exit"
    option=input("Option :")
    if option==1:
        value=input("What Value to Push: ")
        stack.Push(value)
    elif option==2:
        print "Popped: ", stack.Pop()
    elif option==3:
        stack.printL()
    elif option == 4:
        print "Operation Sequence |  Result ",
        for i in range(15):
            num = randint(0,9)
            operation = randint(1,2)
            if operation == 1:
                print "Push: ", num
                stack.Push(num)
            elif operation ==2:
                print "Pop: ", stack.Pop()

        print "\n"
        stack.printL()    
    elif option==5:
        break
    else:
        print "Wrong Option"


1. Push 2. Pop 3. Print 4. Random Testing  5. Exit
Option :4
Operation Sequence |  Result  Pop:  Underflow Error
Push:  6
Pop:  6
Pop:  Underflow Error
Pop:  Underflow Error
Pop:  Underflow Error
Push:  6
Push:  0
Pop:  0
Pop:  6
Pop:  Underflow Error
Pop:  Underflow Error
Push:  5
Push:  5
Push:  2


Head <-- 2 <-- 5 <-- 5 <-- Tail

1. Push 2. Pop 3. Print 4. Random Testing  5. Exit
Option :5

Question 3: Binary Search Tree

Write a program to implement binary search tree. Support:

  1. search
  2. addition
  3. deletion
  4. successor.

Again write a menu base program. (filename: BST)

Answer: From Thomas Coreman, we have following pseduo code:


In [ ]:
class BinarySearchTree:
    def __init__(self):
        """ create an empty binary search tree """
        self.root = None
        
    def search(self ,val):
        return self.recurive_search(self.root, val)
    
    def recurive_search(self, node, val):
        if node == None or val == node.val : return node
        if val < node.val:
            return self.recurive_search(node.left , val)
        else: return self.recurive_search(node.right , val)
        
    def tree_minimum(self, node):
        while node.left != None:
            node = node.left
        return node
            
    def addition(self ,val):
        new_node = TreeNode(val)
        y = None
        x = self.root
        while x != None:
            y=x
            if new_node.val < x.val: x = x.left
            else: x = x.right
        new_node.parent = y
        if y == None: self.root = new_node
        else:
            if new_node.val < y.val: y.left = new_node
            else: y.right = new_node
        
        
    def deletion(self ,node):
        if node.left == None or node.right == None: y = node
        else : y = self.successor(node)
        
        if y.left == None: x = y.left
        else: x = y.right
        if x == None: x.parent = y.parent
            
        if y.parent == None: self.root = x
        elif y == y.parent.left: y.parent.left = x
        else: y.parent.right = x
            
        if y!= node:  node.val = y.val
        return y
        
            
    def successor(self ,node):
        if node.right != None: return self.tree_minimum(node)
        y = node.parent
        while y != None and node == y.right:
            node = y
            y = y.parent
        return y
                    

   
bst=BinarySearchTree()
option = 0
while option != 6:
    print "\n1. Add, 2. Delete, 3. Search, 4. Print, 5. Successor, 6. Exit"
    option=input("Enter Option :")
    if option==1:
        value=input("What Value to add: ")
        bst.addition(value)
    elif option==2:
        value=input("What Value to delete: ")
        bst.deletion(TreeNode(value))
    elif option==3:
        value=input("What Value to search: ")
        temp = bst.search(value)
        if temp == None: print "Not Found"
        else: print "Found"            
    elif option==4:
        print "Printing tree in left to right fashion"
        print_tree(bst.root)
    elif option==5:
        value=input("Whos Successor: ")
        node = bst.successor(bst.search(value))
        if node == None :print "No successor"
        else: print "Successor is: ", node.val
    elif option==6:
        break
    else:
        print "Wrong Option"


1. Add, 2. Delete, 3. Search, 4. Print, 5. Successor, 6. Exit
Enter Option :1
What Value to add: 45

1. Add, 2. Delete, 3. Search, 4. Print, 5. Successor, 6. Exit
Enter Option :1
What Value to add: 65

1. Add, 2. Delete, 3. Search, 4. Print, 5. Successor, 6. Exit
Enter Option :1
What Value to add: 1

1. Add, 2. Delete, 3. Search, 4. Print, 5. Successor, 6. Exit
Enter Option :1
What Value to add: 5

1. Add, 2. Delete, 3. Search, 4. Print, 5. Successor, 6. Exit
Enter Option :4
Printing tree in left to right fashion
   65
45
      5
   1

1. Add, 2. Delete, 3. Search, 4. Print, 5. Successor, 6. Exit

Question 4: Binary Tree Crawler

In this program the computer takes input from the user before performing any operation. The operations that need to be supported are 1. Move 2. Add 3. Print. The program shows a menu:

  1. Move
  2. Add
  3. Print
  4. Exit

If the user picks 1, then the program asks for a movement pattern. For example if the user gives “LLRRL” the program starts from the current node and moves left, again to the left followed by two right movements and finally a left movement. If the movement is not possible then it reports that and stays in the current node otherwise the current node is updated. Further movement starts from the new node. A movement pattern is a string with letters L, R, P, r where L=left, R=Right, P=Parent, r=root. In operation 2 the program tries to add a new node to the left or right of the current node. If the user picks 2, the program asks “Left or Right?”. Suppose the user picks “L” then if the left child of the current node is “Nil” it asks for a value and adds a node with the value as the left child of the current node. If the left child is not nil, it says “Cannot Add, Place not empty”. The print operation prints the binary tree. The output should match the picture of the tree. For example the text based console output may look like

10
/\
/ \
20 11
/ \
/ \
2 8
2

In [8]:
class SearchTreeCrawler():
    def __init__(self):
        """ create an empty binary search tree """
        self.root = None
        self.current = None
        
    def move(self, code):

        if self.current == None or self.root == None: print "\n No node exists."
        elif code == 'L':
            if self.current.left == None: print "\n Cannot Move to: ",code,". Node doesn't exists. Executing Next command.." 
            else:
                self.current = self.current.left
        elif code == 'R':
            if self.current.right == None: print "\n Cannot Move to: ",code,". Node doesn't exists. Executing Next command .." 
            else: self.current = self.current.right
        elif code == 'P':
            self.current = self.current.parent
        elif code == 'r':
            self.current = self.root
            
    def add(self, val):
        temp = TreeNode(val)
        if self.root == None: 
            self.root = temp
            self.current = self.root
        else:
            option = raw_input("L for Left, R for Right: ")
            if option == "L":
                if self.current.left !=None: 
                    print "\n Cannot Add, Place not empty"
                    return None
                self.current.left = temp
                temp.parent = self.current
            elif option == "R":
                if self.current.right !=None:
                    print "\n Cannot Add, Place not empty"
                    return None
                self.current.right = temp
                temp.parent = self.current
            else: print "\n Invalid Selection"
                
    def add_test(self, val, option):
        temp = TreeNode(val)
        if self.root == None: 
            self.root = temp
            self.current = self.root
        else:
            
            if option == "L":
                if self.current.left !=None: 
                    print "\n Cannot Add, Place not empty"
                    return None
                self.current.left = temp
                temp.parent = self.current
            elif option == "R":
                if self.current.right !=None:
                    print "\n Cannot Add, Place not empty"
                    return None
                self.current.right = temp
                temp.parent = self.current
            else: print "\n Invalid Selection"


        

bt = SearchTreeCrawler()
option = 0
while option != 5:
    print "\n1. Move, 2. Add, 3. Print , 4. Random Testing, 5. Exit "
    if bt.current != None: print "Current Node is: ", bt.current.val
    option=input("Enter Option :")
    if option==1:
        value=raw_input("Give movement Pattern: ")
        commands = list(value)
        for code in commands:
            bt.move(code)
    elif option==2:
        value=input("What Value to add: ")
        bt.add(value)
    elif option==3:
        print "\nPrinting tree in left to right fashion:\n"
        print_tree(bt.root)
    elif option == 4:
        from random import randint
        for i in range(4):
            num = randint(0,99)
            opt = i % 2
            if opt == 0: bt.add_test(num, 'L')
            else: bt.add_test(num, 'R')

        print_tree(bt.root)
    elif option==5:
        break
    else:
        print "Wrong Option"


1. Move, 2. Add, 3. Print , 4. Random Testing, 5. Exit 
Enter Option :4

 Cannot Add, Place not empty
     /
   7
     \
  /
11
  \
     /
   70
     \

1. Move, 2. Add, 3. Print , 4. Random Testing, 5. Exit 
Current Node is:  11
Enter Option :5